// Created by WXX on 2021/12/21 21:57
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：76 ms, 在所有 C++ 提交中击败了25.65%的用户
 * 内存消耗：24.7 MB, 在所有 C++ 提交中击败了33.41%的用户
 */
class Solution {
public:

    bool check(int mid, vector<int> &houses, vector<int> &heaters) {
        for (int i = 0, j = 0; i < houses.size(); i++) {
            while (j < heaters.size() && abs(heaters[j] - houses[i]) > mid) j++;
            if (j >= heaters.size()) return false;
        }
        return true;
    }

    int findRadius(vector<int>& houses, vector<int>& heaters) {
        sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());
        int l = 0, r = INT_MAX;
        while (l < r) {
            int mid = (long long)l + r >> 1;
            if (check(mid, houses, heaters)) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};

int main() {

    vector<int> hourses = {1, 2, 3, 4}, heaters = {1, 4};
    cout << Solution().findRadius(hourses, heaters) << endl;  // 1

    return 0;
}
